/**
 * 排序算法 （默认升序排序）
 * 1.冒泡排序
 * 2.选择排序
 * 3.直接插入排序
 * 4.快速排序
 * 5.归并排序
 * 6.希尔排序
 * 7.堆排序
 */
public class Sort {
    public static int arr[] = new int[]{5, 2, 4, 3, 1};

    public static void main(String[] args) {
        // 冒泡排序
        // bulingBulingSort();
        choseSort();
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "---");
        }
    }

    /**
     * 1.冒泡排序
     * 一堆数字 1 5 2 4 3
     * 1.从零开始，下表相近的进行比较，将较大的数往后挪（数据交换），第一轮找到最大的数5
     * 2.重复1步，找到第二、三大的数 4- 3 ，最后排序完成
     */
    public static void bulingBulingSort() {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length - i; j++) {
                // 前一位比后一位大，进行交换
                if (arr[j - 1] > arr[j]) {
                    int tmp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

    /**
     * 2.选择排序
     * 1.遍历一轮 选择最大的数，与最后一位做交换
     * 2.选择倒数第二的数，与倒数第二位做交换
     * 与冒泡排序差不多，区别在于比较后不立即交换数据
     */
    public static void choseSort(){
        for (int i = 0; i < arr.length; i++) {
            int tmp = 0;
            // 找到最大的数据下标
            for (int j = 0; j < arr.length - i; j++) {
                // 前一位比后一位大，进行交换
                if (arr[tmp] < arr[j]) {
                     tmp = j;
                }

            }
            // 交换数据
            int tmpValue = arr[arr.length -i-1];
            arr[arr.length - i-1] = arr[tmp];
            arr[tmp] = tmpValue;
        }
    }
}
